/*
 * robotUniquePath.cpp
 *
 *  Created on: Jul 16, 2012
 *      Author: jh238d
 */

#include <iostream>

using namespace std;

/*backtrack*/
const int M_MAX = 100;
const int N_MAX = 100;

int backtrack(int l, int r, int m, int n, int mat[][N_MAX+2]){
	if(l>m||r>n) return 0;

	if(l==m&&r==n) return 1;

	if(mat[l+1][r]==-1)
		mat[l+1][r]=backtrack(l+1, r, m, n, mat);

	if(mat[l][r+1]==-1)
		mat[l][r+1]=backtrack(l, r+1, m, n, mat);

	return mat[l+1][r]+mat[l][r+1];

}

int backtrack(int m, int n){
	int mat[M_MAX+2][N_MAX+2];
	for(int i=0; i<M_MAX+2; i++)
		for(int j=0; j<N_MAX+2; j++)
			mat[i][j] = -1;

	return backtrack(1, 1, m, n, mat);
}

/* DP */

int unique_path_DP(int m, int n){
	int mat[M_MAX+2][N_MAX+2] = {0};
	mat[m][n+1]=1;

	for(int i=m; i>=1; i--)
		for(int j=n;j>=1; j--)
			mat[i][j]=mat[i+1][j]+mat[i][j+1];

	return mat[1][1];
}

int main(){
	cout << backtrack(3, 7);
	cout<< endl;
	cout << unique_path_DP(3, 7);
	return 0;
}
